package leetcode.editor.cn.dsa09_doublequeue;
//给定一个字符串，逐个翻转字符串中的每个单词。

public class ReverseWordsInAString151_1 {
    public static void main(String[] args) {
        ReverseWordsInAString151_1.Solution solution = new ReverseWordsInAString151_1().new Solution();
        System.out.println(solution.reverseWords("the sky is blue"));
        System.out.println(solution.reverseWords("  hello world!  "));
        System.out.println(solution.reverseWords("a good   example"));
        System.out.println(solution.reverseWords("  Bob    Loves  Alice   "));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法二：数组+双指针实现思路二
         * 1.按字符串长度定义新数组，临时存储
         * 2.倒序遍历字符串，定位单词起止索引
         * 3.读取单词起止索引范围内的字符，写入新数组
         * 4.还原指针，用以定位下个单词
         * 5.将新数组中合法数据生成新字符串
         * 边界问题
         *   以字符串中的空格为单词分界
         *   字符串首尾的空格应跳过
         * 细节问题
         *   倒序遍历时，先定义单词尾指针
         *   读取到下一个空格，索引+1定位单词开始指针
         *   注意单词间的多个空格，只保留一个
         *
         * @param s
         * @return
         */
        public String reverseWords(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) {
                return "";
            }
            // 1.准备工作：初始化新数组，定义单词起止索引
            char[] chars = new char[len]; // 新字符数组
            int first = -1, last = -1, index = 0; // 单词起止索引
            // 2.倒序遍历字符串，定位单词起止索引
            for (int i = len - 1; i >= 0; i--) {
                char c = s.charAt(i);
                if (c != ' ') { // 非空格：第一个非空格为单词结尾字符
                    if (last == -1) last = i; // 2.1. 定位last
                    if (i == 0) first = 0; // 处理字符串首字符不是空格
                } else { // 空格：以“空格+1”为单词开始索引
                    if (last != -1) first = i + 1; // 2.2.定位first
                }
                // 3.读取单词起止索引范围内的字符，写入新数组
                if (first >= 0 && last >= 0) {
                    // 如果新数组中已经有数据，先存放一个空格，再放数据
                    if (index > 0) chars[index++] = ' ';
                    while (first <= last) {
                        chars[index++] = s.charAt(first++);
                    }
                    // 4.还原指针，用以定位下个单词
                    first = last = -1;
                }
            }
            // 5.将新数组中合法数据生成新字符串返回
            return new String(chars, 0, index);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}